﻿/// <summary>
/// https://leetcode-cn.com/problems/permutations/
/// </summary>
public class Solution
{
    private IEnumerable<int> RemoveOne(IEnumerable<int> values, int value)
    {
        bool removed = false;
        foreach (var val in values)
        {
            if (val == value && !removed)
            {
                removed = true;
                continue;
            }
            yield return val;
        }
    }

    private IEnumerable<IEnumerable<int>> Permute(IEnumerable<int> nums, IEnumerable<int> cur)
    {
        if (!nums.Any())
            return new IEnumerable<int>[] { cur };

        var result = new List<IEnumerable<int>>();
        foreach (var num in nums)
            result.AddRange(this.Permute(this.RemoveOne(nums, num), cur.Concat(new int[] { num })));
        return result;
    }

    public IList<IList<int>> Permute(int[] nums)
    {
        List<IList<int>> result = new List<IList<int>>();
        foreach (var p in this.Permute(nums, Array.Empty<int>()))
            result.Add(new List<int>(p));
        return result;
    }
}